//中位数是有序整数列表中的中间值。如果列表的大小是偶数，则没有中间值，中位数是两个中间值的平均值。 
//
// 
// 例如 arr = [2,3,4] 的中位数是 3 。 
// 例如 arr = [2,3] 的中位数是 (2 + 3) / 2 = 2.5 。 
// 
//
// 实现 MedianFinder 类: 
//
// 
// MedianFinder() 初始化 MedianFinder 对象。 
// void addNum(int num) 将数据流中的整数 num 添加到数据结构中。 
// double findMedian() 返回到目前为止所有元素的中位数。与实际答案相差 10⁻⁵ 以内的答案将被接受。 
// 
//
// 示例 1： 
//
// 
//输入
//["MedianFinder", "addNum", "addNum", "findMedian", "addNum", "findMedian"]
//[[], [1], [2], [], [3], []]
//输出
//[null, null, null, 1.5, null, 2.0]
//
//解释
//MedianFinder medianFinder = new MedianFinder();
//medianFinder.addNum(1);    // arr = [1]
//medianFinder.addNum(2);    // arr = [1, 2]
//medianFinder.findMedian(); // 返回 1.5 ((1 + 2) / 2)
//medianFinder.addNum(3);    // arr[1, 2, 3]
//medianFinder.findMedian(); // return 2.0 
//
// 提示: 
//
// 
// -10⁵ <= num <= 10⁵ 
// 在调用 findMedian 之前，数据结构中至少有一个元素 
// 最多 5 * 10⁴ 次调用 addNum 和 findMedian 
// 
//
// Related Topics 设计 双指针 数据流 排序 堆（优先队列） 👍 811 👎 0


//leetcode submit region begin(Prohibit modification and deletion)
class MedianFinder {

        private Heap right;
        private Heap left;


    public MedianFinder() {
        right=new Heap(10,false);
        left=new Heap(10,true);
    }
    
    public void addNum(int num) {
        if(left.size()== right.size()){
            right.offer(num);
            left.offer(right.poll());
        }else{
            left.offer(num);
            right.offer(left.poll());
        }
    }
    
    public double findMedian() {
        if(left.size()==right.size()){
            return (left.peek()+ right.peek())/2.0;

        }else{
            return left.peek();
        }
    }

    class Heap{
        private int size=0;
        private int [] arry;

        private Boolean max;


        public Heap(int size) {
            this.size = size;
        }
        public int size(){
            return  size;
        }

        public Heap(int capaticy, Boolean max) {
            arry = new int[capaticy];
            this.max = max;
        }

        public void swap(int i,int j){
            int tem=arry[i];
            arry[i]=arry[j];
            arry[j]=tem;
        }

        public int peek(){
            return arry[0];
        }

        public void offer(int offered){
            if(size==arry.length){
                grow();
            }
            up(offered);
            size++;
        }

        public void up(int offered){
            int child=size;
            while (child>0){
                int parent=(child-1)/2;
                Boolean tem=max?offered>arry[parent]:offered<arry[parent];
                if (tem){
                    arry[child]=arry[parent];
                }else {
                    break;
                }
                child=parent;
            }
            arry[child]=offered;
        }

        public void down(int parent){
            int left=parent*2+1;
            int right=left+1;
            int min=parent;
            if(left<size&&(max?arry[left]>arry[min]:arry[left]<arry[min])){
                min=left;
            }
            if (right<size&&(max?arry[right]>arry[min]:arry[right]<arry[min])){
                min=right;
            }
            if(min!=parent){
                swap(min,parent);
                down(min);
            }
        }

        public int poll(){
            int num=arry[0];
            swap(0,size-1);
            size--;
            down(0);
            return num;
        }


        public void grow(){
            int capacity=size+(size >>1);
            int[] newArray = new int[capacity];
            System.arraycopy(arry,0,newArray,0,size);
            arry=newArray;
        }



    }
}

/**
 * Your MedianFinder object will be instantiated and called as such:
 * MedianFinder obj = new MedianFinder();
 * obj.addNum(num);
 * double param_2 = obj.findMedian();
 */
//leetcode submit region end(Prohibit modification and deletion)
